package com.example.Arithmetic.Lettcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 日期：2024/1/3
 * 时间：10:24
 * 描述：组合，一个数字可以和另外一个数字有多少种组合，不是排列
 * 回溯思想
 */
public class E01Lettcode77 {
    public static List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> list = new ArrayList<>();
        dfs(1, n, k, list, new LinkedList());
        return list;
    }

    private static void dfs(int start, int n, int k, List<List<Integer>> list, LinkedList stack) {
//        结束条件
        if (stack.size() == k) {
            list.add(new ArrayList<>(stack));
            return;
        }
        for (int i = start; i <= n; i++) {
//            缺的数字个数>备用数字
            if (k - stack.size() > n - i + 1){
                break;
            }
            stack.push(i);
            dfs(i + 1, n, k, list, stack);
            stack.pop();
        }
    }

    public static void main(String[] args) {
        List<List<Integer>> lists = combine(5, 2);
        for (List<Integer> list : lists) {
            System.out.println(list);
        }
    }
}

